package stack_queue;

import java.util.Stack;

/**
 * 20. 有效的括号
 * 使用Stack
 *
 * @author Api
 * @date 2023/10/15 23:19
 */
public class Code20_ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        if (s == null || s.isEmpty() || s.length() % 2 != 0) {
            return false;
        }
        // 仅需要判断三种情况
        // 1. ([{}]()
        // 2. [{(]}]
        // 3. [{}]())))
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            // 碰到左括号，就把相应的右括号入栈
            if ('[' == chars[i]) {
                stack.push(']');
            } else if ('{' == chars[i]) {
                stack.push('}');
            } else if ('(' == chars[i]) {
                stack.push(')');
            } else if (stack.isEmpty() || stack.peek() != chars[i]) { // 如果是右括号判断是否和栈顶元素匹配，情况2和3
                return false;
            } else {
                stack.pop();
            }
        }
        // 最后判断栈中元素是否匹配(情况3)
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}
